#include <vector>
using namespace std;
#include <set>
#include <algorithm>


// version 1 
class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0, right = nums.size() - 1;
        while(left <= right){
            int mid = (right + left) / 2;
            //这里很容易出现一个问题，就是直接拿(left + right) / 2 得到中间点会有溢出风险
            //所以，我们可以使用另一种方式
            //int mid = left + (right - left) / 2;
            if(nums[mid] < target) left = ++mid;
            else if(nums[mid] == target) return mid;
            else right = --mid;
        }
        return -1;
    }
};
//这是最简单的二分模板